The Fast Fourier Transform (FFT) is the generic name for a class of computationally efficient algorithms that implement the Discrete Fourier Transform (DFT) and are widely used in the field of digital signal processing. With the advent of digital signal processors (DSP), near real time digital signal processing has become possible. However, circuit designers are still striving for faster and better FFT devices. In a typical computing system, the most time consuming operation is usually associated with memory. This is evident in the many schemes which have been developed to boost memory access time to increase the overall speed of computing systems.
The FFT algorithm is especially memory access and storage intensive. For example, in order to compute a radix-4 decimation-in-frequency (DIF) FFT butterfly, four data samples and three twiddle coefficients are read from memory and four resultant data samples are written back into memory. In an N-point radix-4 DIF FFT, there are a total of 2N log4 N pieces of data and intermediate data to be accessed and stored and a total of (3N/4)log4 N twiddle coefficients to be accessed. In other words, to compute a 64-point radix-4 DIF FFT, 192 data memory reads and 192 data memory writes and 144 memory reads for the twiddle coefficients must be performed. Accordingly, it is desirable to provide adequate memory arrangement to accommodate all the data and coefficients.
In computing the FFT butterflies going from one stage to the next, the output data of the butterfly computations of the former become the input data of the latter, where the order and grouping of the data vary from one stage to the next. It is therefore necessary to ensure that correct data is accessed from memory for each butterfly computation.
To further increase speed, a fully parallel implementation of an FFT circuit may be desirable. In such a parallel FFT circuit, it is preferable that the four pieces of data and the three twiddle coefficients are available substantially simultaneously for each butterfly computation.
It is apparent from the foregoing that memory access for an FFT circuit is not trivial. Not only a large number of data are accessed from memory, but a large number of resultant data are also stored back into memory for use in future computations. For each butterfly computation, the data and twiddle coefficient must also be obtained substantially simultaneously. Furthermore, for each memory access and storage operation, the address must be correctly computed and referenced.
Wireless cellular communication networks incorporate a number of mobile UEs and a number of NodeBs. A NodeB is generally a fixed station, and may also be called a base transceiver system (BTS), an access point (AP), a base station (BS), or some other equivalent terminology. As improvements of networks are made, the NodeB functionality evolves, so a NodeB is sometimes also referred to as an evolved NodeB (eNB). In general, NodeB hardware, when deployed, is fixed and stationary, while the UE hardware is portable.
In contrast to NodeB, the mobile UE can comprise portable hardware. User equipment (UE), also commonly referred to as a terminal or a mobile station, may be fixed or mobile device and may be a wireless device, a cellular phone, a personal digital assistant (PDA), a wireless modem card, and so on. Uplink communication (UL) refers to a communication from the mobile UE to the NodeB, whereas downlink (DL) refers to communication from the NodeB to the mobile UE. Each NodeB contains radio frequency transmitter(s) and the receiver(s) used to communicate directly with the mobiles, which move freely around it. Similarly, each mobile UE contains radio frequency transmitter(s) and the receiver(s) used to communicate directly with the NodeB. In cellular networks, the mobiles cannot communicate directly with each other but have to communicate with the NodeB.
In the Universal Mobile Telecommunications System (UMTS/HSxPA) specifications, systems are capable of supporting high speed packet access for both downlink (up to 14 Mbps) and uplink (up to 5.76 Mbps). Although HSxPA systems offer substantial improvement for packet data transmission over earlier UMTS systems, their designs were limited by compatibility requirements with previous generations of UMTS specifications. With the emergence of OFDM-based mobile broadband systems such as WiMAX 802.16e, a comprehensive long term evolution (LTE) of UMTS was required to remain competitive in the long term. As a result, work was begun on LTE Evolved UMTS Terrestrial Radio Access (E-UTRA). Long term goals for the system include support for high peak data rates (100 Mbps downlink and 50 Mbps uplink), low latency (10 ms round-trip delay), improved system capacity and coverage, reduced operating costs, multi-antenna support, efficient support for packet data transmission, flexible bandwidth operations (up to 20 MHz) and seamless integration with existing systems.
Control information bits are transmitted from each mobile to the NodeB in the uplink (UL), for example, for several purposes. The control information is typically required to be highly reliable in order to support an appropriate and accurate operation. This uplink control information is typically transmitted using the physical uplink control channel (PUCCH), as defined by the 3GPP working groups (WG), for evolved universal terrestrial radio access (EUTRA). The EUTRA is sometimes also referred to as 3GPP long-term evolution (3GPP LTE). The structure of the PUCCH is designed to provide sufficiently high transmission reliability. In addition to PUCCH, the EUTRA standard also defines a physical uplink shared channel (PUSCH), intended for transmission of uplink user data. The general operations of the physical channels are described in the EUTRA specifications, for example: “3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (E-UTRA); Physical Channels and Modulation” (3GPP TS 36.211, Release 8). Modulation and demodulation of the control data and user data passed between the base station and mobile UE is performed using DFT and inverse DFT calculations.